রিকারশন (Recursion) কী?
রিকারশন হলো একটি প্রক্রিয়া যেখানে একটি ফাংশন নিজেই নিজেকে কল করে এবং সমস্যাকে ছোট ছোট উপ-সমস্যায় ভাগ করে সমাধান করে। রিকারশন সাধারণত এমন সমস্যার সমাধানে ব্যবহৃত হয় যেগুলোতে পুনরাবৃত্তি প্রয়োজন হয় এবং সমস্যাটি স্বাভাবিকভাবে নিজের মতো দেখতে লাগে।
রিকারশন দুটি অংশে বিভক্ত:
- বেস কেস (Base Case): যেখানে রিকারশন থেমে যায়।
- রিকার্সিভ কেস (Recursive Case): যেখানে ফাংশন নিজেকে পুনরায় কল করে এবং সমস্যাকে আরও ছোট করে।
রিকারশন কিভাবে কাজ করে?
রিকারশন মূলত সমস্যাটিকে ধাপে ধাপে ছোট করতে থাকে এবং প্রতিটি ধাপের সমাধান করতে থাকে যতক্ষণ না বেস কেসে পৌঁছে। বেস কেসে পৌঁছানোর পর ফাংশন নিজেকে কল করা বন্ধ করে এবং তার আগে জমা হওয়া সব কলগুলো একে একে সমাধান করতে থাকে।
রিকারশনের উদাহরণ
উদাহরণ ১: ফ্যাক্টোরিয়াল গণনা
ফ্যাক্টোরিয়াল গণনা করা রিকারশনের একটি ক্লাসিক উদাহরণ, যেখানে n! = n * (n-1)!।
সাধারণত:
n = 0বাn = 1হলে,n! = 1(বেস কেস)।- অন্যথায়,
n! = n * (n-1)!(রিকার্সিভ কেস)।
Python কোড:
def factorial(n):
if n == 0 or n == 1: # বেস কেস
return 1
else:
return n * factorial(n - 1) # রিকার্সিভ কেস
print(factorial(5)) # আউটপুট: 120
এখানে factorial(5) নিজেই নিজেকে কল করতে থাকে যতক্ষণ না n = 1 এ পৌঁছে। তখন এটি ফলাফল রিটার্ন করে এবং ফলাফলগুলোকে ধাপে ধাপে গুণ করে।
উদাহরণ ২: ফিবোনাচি সিরিজ
ফিবোনাচি সিরিজে প্রতিটি সংখ্যা পূর্বের দুটি সংখ্যার যোগফল। যেমন: 0, 1, 1, 2, 3, 5, 8...
সাধারণত:
n = 0হলেfib(0) = 0n = 1হলেfib(1) = 1- অন্যথায়,
fib(n) = fib(n-1) + fib(n-2)
Python কোড:
def fibonacci(n):
if n == 0: # বেস কেস
return 0
elif n == 1: # বেস কেস
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2) # রিকার্সিভ কেস
print(fibonacci(6)) # আউটপুট: 8
এখানে fibonacci(6) কল করলে এটি ধাপে ধাপে ছোট উপ-সমস্যাগুলিকে সমাধান করতে থাকে।
রিকারশনের সুবিধা এবং অসুবিধা
সুবিধা:
- কোড সহজে বোঝা যায়: জটিল সমস্যার জন্য রিকারশনে কোড সংক্ষিপ্ত এবং সহজ হয়।
- ছোট সমস্যার সমাধানে কার্যকর: নির্দিষ্ট সমস্যা, যেমন ফ্যাক্টোরিয়াল বা ফিবোনাচি, সহজে সমাধান করা যায়।
- ডিভাইড অ্যান্ড কনকোয়ার স্ট্র্যাটেজি: বড় সমস্যাগুলোকে ছোট ছোট অংশে ভেঙে সমাধান করা যায়।
অসুবিধা:
- টাইম কমপ্লেক্সিটি: নির্দিষ্ট সমস্যায় টাইম কমপ্লেক্সিটি অনেক বেশি হয়ে যায়, বিশেষ করে ফিবোনাচি সমস্যায়।
- স্ট্যাক ওভারফ্লো: অতিরিক্ত রিকারশন হলে স্ট্যাক ওভারফ্লো হতে পারে।
- অতিরিক্ত মেমরি খরচ: প্রত্যেকটি ফাংশন কল স্ট্যাক মেমরিতে জমা হয়, যা মেমরি খরচ বাড়ায়।
রিকারশন বনাম ইটারেশন
| বৈশিষ্ট্য | রিকারশন | ইটারেশন |
|---|---|---|
| কোডিং স্টাইল | কোড সহজ ও সংক্ষিপ্ত হয় | লুপের মাধ্যমে সমাধান করা হয় |
| মেমরি খরচ | স্ট্যাক মেমরি ব্যবহৃত হয় | অতিরিক্ত মেমরি ব্যবহার হয় না |
| টাইম কমপ্লেক্সিটি | নির্দিষ্ট ক্ষেত্রে বেশি হতে পারে | তুলনামূলকভাবে কম খরচ হয় |
| কার্যক্ষমতা | ছোট সমস্যার জন্য কার্যকর | বড় সমস্যার জন্য কার্যকর |
উপসংহার
রিকারশন প্রোগ্রামিংয়ে একটি শক্তিশালী কৌশল যা বড় সমস্যাকে ছোট ছোট উপ-সমস্যায় ভাগ করে সমাধান করতে সহায়ক। সঠিকভাবে ব্যবহৃত হলে এটি কোডিংকে সহজ এবং কার্যকর করে তোলে, তবে অতিরিক্ত রিকারশন স্ট্যাক ওভারফ্লো এবং মেমরি খরচের কারণ হতে পারে।
Read more
